#ifndef PARALLELIZABLE_H_
#define PARALLELIZABLE_H_

#include "ArrayOrderedSet.h"
#include "ArrayvEBTree.h"
#include "BitTools.h"
#include "OrderedSet.h"
#include "vEBTree.h"

/*!
 * \class ParalelizableOperation
 *
 * This class represents operations that can be made faster by
 * using the bit parallel technique.
 *
 *
 */
template<typename T>
class ParalelizableOperation{

protected:
	/*!
	 *
	 */
	friend class ArrayOrderedSet<T>;

	/*!
	 *
	 */
	friend class ArrayvEBTree<T>;

	/*!
	 *
	 */
	friend class OrderedSet<long>;

	/*!
	 *
	 */
	friend class vEBTree<T>;

public:

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(OrderedSet<long>* a, OrderedSet<long>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(OrderedSet<long>* a, OrderedSet<long>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(OrderedSet<long>* a, ArrayOrderedSet<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(OrderedSet<long>* a, ArrayOrderedSet<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(OrderedSet<long>* a, vEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(OrderedSet<long>* a, vEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(OrderedSet<long>* a, ArrayvEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(OrderedSet<long>* a, ArrayvEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(ArrayOrderedSet<T>* a, OrderedSet<long>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(ArrayOrderedSet<T>* a, OrderedSet<long>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(ArrayOrderedSet<T>* a, ArrayOrderedSet<T>* b);


	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(ArrayOrderedSet<T>* a, ArrayOrderedSet<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(ArrayOrderedSet<T>* a, vEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(ArrayOrderedSet<T>* a, vEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(ArrayOrderedSet<T>* a, ArrayvEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(ArrayOrderedSet<T>* a, ArrayvEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(vEBTree<T>* a, OrderedSet<long>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(vEBTree<T>* a, OrderedSet<long>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(vEBTree<T>* a, ArrayOrderedSet<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(vEBTree<T>* a, ArrayOrderedSet<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(vEBTree<T>* a, vEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(vEBTree<T>* a, vEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(vEBTree<T>* a, ArrayvEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(vEBTree<T>* a, ArrayvEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(ArrayvEBTree<T>* a, OrderedSet<long>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(ArrayvEBTree<T>* a, OrderedSet<long>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(ArrayvEBTree<T>* a, ArrayOrderedSet<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(ArrayvEBTree<T>* a, ArrayOrderedSet<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(ArrayvEBTree<T>* a, vEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(ArrayvEBTree<T>* a, vEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setUnion(ArrayvEBTree<T>* a, ArrayvEBTree<T>* b);

	/*!
	 * \brief
	 *
	 * \param a
	 * \param b
	 */
	static void setIntersec(ArrayvEBTree<T>* a, ArrayvEBTree<T>* b);

};

template<typename T>
void ParalelizableOperation<T>::setUnion(OrderedSet<long>* a, OrderedSet<long>* b){
	a->setUnionSet(b);
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(OrderedSet<long>* a, OrderedSet<long>* b){
	a->setIntersecSet(b);
}

template<typename T>
void ParalelizableOperation<T>::setUnion(OrderedSet<long>* a, ArrayOrderedSet<T>* b){
	T* vec = b->vector;
	T* lim = vec + b->vectorsz;
	long offset = 0;
	long size = b->sizeb;
	long look;
	for(; vec < lim; vec++, offset += size, look = 0){
		look = builtinLeast<T>(*vec & posmasklsimp[look]);
		while(look != -1){
			a->toSet(offset + look);
			look++;
			if(look < size)look = builtinLeast<T>(*vec & posmasksimp[look]);
			else look = -1;
		}
	}
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(OrderedSet<long>* a, ArrayOrderedSet<T>* b){
	a->setIntersecSet(b);
}

template<typename T>
void ParalelizableOperation<T>::setUnion(OrderedSet<long>* a, vEBTree<T>* b){
	long next = 0;
	long size = b->size();
	next = b->nextSetElement(next);
	while(next < size - 1){
		a->toSet(next++);
		next = b->nextSetElement(next);
	}
	if(b->isInSet(size-1))a->toSet(size-1);
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(OrderedSet<long>* a, vEBTree<T>* b){
	a->setIntersecSet(b);
}

template<typename T>
void ParalelizableOperation<T>::setUnion(OrderedSet<long>* a, ArrayvEBTree<T>* b){
	T* vec = b->vector;
	T* lim = vec + b->vectorsz;
	long offset = 0;
	long size = b->sizeb;
	long look;
	for(; vec < lim; vec++, offset += size, look = 0){
		look = builtinLeast<T>(*vec & posmasklsimp[look]);
		while(look != -1){
			a->toSet(offset + look);
			look++;
			if(look < size)look = builtinLeast<T>(*vec & posmasksimp[look]);
			else look = -1;
		}
	}
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(OrderedSet<long>* a, ArrayvEBTree<T>* b){
	long next = 0;
	long size = b->size();
	next = b->nextSetElement(next);
	while(next < size - 1){
		;
		next = b->nextSetElement(next);
	}
	if(b->isInSet(size-1))a->toSet(size-1);
}


template<typename T>
void ParalelizableOperation<T>::setUnion(ArrayOrderedSet<T>* a, OrderedSet<long>* b){
	long next = 0;
	long size = b->size();
	T* vec = a->vector;
	T maskb = a->maskb;
	next = b->nextSetElement(next);
	while(next < size - 1){
		*(vec + next) |= (1LL << (next & maskb));
		next++;
		next = b->nextSetElement(next);
	}
	if(b->isInSet(size-1))a->toSet(size-1);
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(ArrayOrderedSet<T>* a, OrderedSet<long>* b){
	T* vec = a->vector;
	T* lim = vec + a->vectorsz;
	long offset = 0;
	long size = a->sizeb;
	long look;
	T maskb = a->maskb;
	for(; vec < lim; vec++, offset += size, look = 0){
		look = builtinLeast<T>(*vec & posmasklsimp[look]);
		while(look != -1){
			if(a->isInCompl(offset + look)){
				*(vec + offset) &= ~(1LL << (look & maskb));
			}
			look++;
			if(look < size)look = builtinLeast<T>(*vec & posmasksimp[look]);
			else look = -1;
		}
	}
}

template<typename T>
void ParalelizableOperation<T>::setUnion(ArrayOrderedSet<T>* a, ArrayOrderedSet<T>* b){
	T* avec = a->vector;
	T* bvec = b->vector;
	T* lim = avec + a->vectorsz;
	for(; avec < lim; avec++, bvec++) *avec |= *bvec;
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(ArrayOrderedSet<T>* a, ArrayOrderedSet<T>* b){
	T* avec = a->vector;
	T* bvec = b->vector;
	T* lim = avec + a->vectorsz;
	for(; avec < lim; avec++, bvec++) *avec &= *bvec;
}

template<typename T>
void ParalelizableOperation<T>::setUnion(ArrayOrderedSet<T>* a, vEBTree<T>* b){
	T* avec = a->vector;
	long bvec = 0;
	T* lim = avec + a->vectorsz;
	for(; avec < lim; avec++, bvec++) *avec |= b->treeNode(bvec);
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(ArrayOrderedSet<T>* a, vEBTree<T>* b){
	T* avec = a->vector;
	long bvec = 0;
	T* lim = avec + a->vectorsz;
	for(; avec < lim; avec++, bvec++) *avec |= b->treeNode(bvec);
}

template<typename T>
void ParalelizableOperation<T>::setUnion(ArrayOrderedSet<T>* a, ArrayvEBTree<T>* b){
	T* avec = a->vector;
	T* bvec = b->vector;
	T* lim = avec + a->vectorsz;
	for(; avec < lim; avec++, bvec++) *avec |= *bvec;
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(ArrayOrderedSet<T>* a, ArrayvEBTree<T>* b){
	T* avec = a->vector;
	T* bvec = b->vector;
	T* lim = avec + a->vectorsz;
	for(; avec < lim; avec++, bvec++) *avec &= *bvec;
}


template<typename T>
void ParalelizableOperation<T>::setUnion(vEBTree<T>* a, OrderedSet<long>* b){
	T word;
	long size = a->sizeInWord();
	long offset;
	long sizeb = sizeof(T)*8;
	if(a->height > 1){
		for(long i = 0; i < size;i++, offset+= sizeb){
			word = 0;
			for(long j = 0; j < sizeb; j++){
				if(b->isInSet(offset + j)) word |= (1LL << j);
			}
			a->setNode(i, word | a->getNode(i));
		}
	}else{
		for(long i = 0; i < size;i++, offset+= sizeb){
			word = 0;
			for(long j = 0; j < sizeb; j++){
				if(b->isInSet(offset + j)) word |= (1LL << j);
			}
			a->setNodeInLevel(i, word | a->getNode(i));
		}
	}
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(vEBTree<T>* a, OrderedSet<long>* b){
	long offset = 0;
	long look = 0;
	long size = a->size();
	long sizeb = sizeof(T)*8;
	if(a->height > 1){
		for(long i = a->levels[1]->nextSetElement(0); i < size-1; i = a->levels[1]->nextSetElement(i+1), offset += sizeb){
			look = a->nextSetInWord(offset);
			while(look != -1){
				if(b->isInCompl(offset+ look))a->toCompl(offset+look);
				look++;
				if(look < sizeb)look = a->nextSetInWord(offset);
				else look = -1;
			}
		}
		offset += sizeb;

		//necessary to the last word
		look = a->nextSetInWord(offset);
		while(look != -1){
			if(b->isInCompl(offset+ look))a->toCompl(offset+look);
			look++;
			if(look < sizeb)look = a->nextSetInWord(offset);
			else look = -1;
		}

	}else{
		for(long i = 0; i < size; i++, offset+= sizeb){
			look = a->nextSetInWord(offset);
			while(look != -1){
				if(b->isInCompl(offset+ look))a->toCompl(offset+look);
				look++;
				if(look < sizeb)look = a->nextSetInWord(offset);
				else look = -1;
			}
		}
	}
}

template<typename T>
void ParalelizableOperation<T>::setUnion(vEBTree<T>* a, ArrayOrderedSet<T>* b){
	T* bvec = b->vector;
	T* lim = bvec + b->vectorsz;
	if(a->height > 1){
		for(long i = 0; bvec < lim; bvec++, i++)
			if(*bvec != 0)a->setNode(i, a->getNode(i)|*bvec);
	}
	else{
		for(long i = 0; bvec < lim; bvec++, i++)
			if(*bvec != 0)a->setNodeInLevel(i, a->getNode(i)|*bvec);
	}
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(vEBTree<T>* a, ArrayOrderedSet<T>* b){
	long size = a->size();
	T* bvec = b->vector;
	if(a->height > 1){
		for(long i = a->levels[1]->nextSetElement(0); i < size-1; i = a->levels[1]->nextSetElement(i+1)){
			a->setNode(i, a->getNode(i) & *(bvec + i));
		}
	}else{
		for(long i = 0; i < size; i++){
			a->setNodeInLevel(i, a->getNode(i) & *(bvec + i));
		}
	}
}

template<typename T>
void ParalelizableOperation<T>::setUnion(vEBTree<T>* a, vEBTree<T>* b){
	a->setUnionSet(b);
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(vEBTree<T>* a, vEBTree<T>* b){
	a->setIntersecSet(b);
}

template<typename T>
void ParalelizableOperation<T>::setUnion(vEBTree<T>* a, ArrayvEBTree<T>* b){
	a->setUnionSet(b);
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(vEBTree<T>* a, ArrayvEBTree<T>* b){
	b->setIntersecSet(b);
}



template<typename T>
void ParalelizableOperation<T>::setUnion(ArrayvEBTree<T>* a, OrderedSet<long>* b){
	long offset = 0;
	long look = 0;
	long size = a->sizeInWords();
	long sizeb = sizeof(T)*8;
	T word;

	for(long i = 0; i < size; i++, offset += sizeb, word = a->getNode(i)){
		for(long j = 0; j < sizeb; j++){
			if(b->isInSet(offset + j)) word |= (1LL << j);
		}
		a->setNode(i, word);
	}
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(ArrayvEBTree<T>* a, OrderedSet<long>* b){
	long offset = 0;
	long look = 0;
	long size = a->sizeInWords();
	long sizeb = sizeof(T)*8;
	T word;

	for(long i = 0; i < size; i++, offset += sizeb, word = a->getNode(i)){
		for(long j = 0; j < sizeb; j++){
			if(b->isInCompl(offset + j)) word &= ~(1LL << j);
		}
		a->setNode(i, word);
	}
}

template<typename T>
void ParalelizableOperation<T>::setUnion(ArrayvEBTree<T>* a, ArrayOrderedSet<T>* b){
	T* avec = a->vector;
	T* bvec = b->vector;
	T* lim = avec + a->vectorsz;
	long size = a->vectorsz;

	for(long i = 0; i < size; i++, avec++, bvec++)a->setNode(i, *avec|*bvec);
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(ArrayvEBTree<T>* a, ArrayOrderedSet<T>* b){
	T* avec = a->vector;
	T* bvec = b->vector;
	T* lim = avec + a->vectorsz;
	long size = a->vectorsz;

	if(a->height > 1){
		ArrayvEBTree<T>* up = a->levels[1];
		for(long i = up->nextSetElement(0); i < size - 1; i = up->nextSetElement(i+1)){
			a->setNode(i, avec[i]&bvec[i]);
		}
		a->setNode(size-1, avec[size-1]&bvec[size-1]);
	}else{
		for(long i = 0; i < size; i++, avec++, bvec++)a->setNodeInLevel(i, *avec|*bvec);
	}
}

template<typename T>
void ParalelizableOperation<T>::setUnion(ArrayvEBTree<T>* a, vEBTree<T>* b){
	a->setUnionSet(b);
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(ArrayvEBTree<T>* a, vEBTree<T>* b){
	a->setIntersecSet(b);
}

template<typename T>
void ParalelizableOperation<T>::setUnion(ArrayvEBTree<T>* a, ArrayvEBTree<T>* b){
	a->setUnionSet(b);
}

template<typename T>
void ParalelizableOperation<T>::setIntersec(ArrayvEBTree<T>* a, ArrayvEBTree<T>* b){
	a->setIntersecSet(b);
}

#endif
